//
//  53. 最大子序列和.swift
//  Top600
//
//  Created by rjb on 2021/7/30.
//

import Foundation
class Solution53 {
    // 最大和的连续子数组
    // 不断计算数组
    // 定义dp[i] 表示以i结尾的最大子数组和
    // 因为只用到了上一组的值
    // 这个其实就是一个动态规划
    var result: Int = Int.min
    func maxSubArray(_ nums: [Int]) -> Int {
        var dp = Array(repeating: 0, count: nums.count + 1)
        for i in 1..<dp.count {
            let v = nums[i - 1]
            dp[i] = max(dp[i - 1] + v, v)
            result = max(result, dp[i])
        }
        return result
    }
    static func test() {
        let solution = Solution53()
//        let nums = [-2,1,-3,4,-1,2,1,-5,4]
        let nums = [-1]
        let result = solution.maxSubArray(nums)
        print(result)
    }
}
